package org.lan.interview.search;

import java.util.Arrays;

/**
 * 排序算法
 * <a href="https://github.com/hustcc/JS-Sorting-Algorithm"> GitBook 在线书籍 《十大经典排序算法》</a>
 *
 * @author <p><a href="mailto:1728209643@qq.com">XiaoSan</a>
 * @date 2019/11/18 1:32 PM
 */
public class Sorter {

    /**
     * 直接插入排序
     * 每一步将一个待排序的元素，按其大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止
     *
     * @param arr arr
     * @return 原数组
     */
    public static int[] insert(int[] arr) {
        return insert(arr, 1);
    }

    /**
     * 插入排序
     *
     * @param arr arr
     * @param gap 比较元素的步长
     * @return 原数组
     */
    private static int[] insert(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j - gap >= 0; j--) {
                if (arr[j] < arr[j - gap]) {
                    swap(j, j - gap, arr);
                } else {
                    break;
                }
            }
        }
        return arr;
    }

    /**
     * 希尔排序
     * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
     * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
     * 然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，
     * 即所有记录放在同一组中进行直接插入排序为止。
     *
     * @param arr arr
     * @return 原数组
     */
    public static int[] shell(int[] arr) {
        for (int gap = arr.length >> 1; gap > 0; gap >>= 1) {
            insert(arr, gap);
        }

        return arr;
    }


    /**
     * 冒泡排序
     * <p>
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * <p>
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     * <p>
     * 针对所有的元素重复以上的步骤，除了最后一个。
     * <p>
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     *
     * @param arr arr
     * @return arr
     */
    public static int[] bubble(int[] arr) {
        boolean flag = Boolean.TRUE;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j + 1] < arr[j]) {
                    swap(j, j + 1, arr);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return arr;
    }


    /**
     * 选择排序
     * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
     * <p>
     * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     * <p>
     * 重复第二步，直到所有元素均排序完毕。
     *
     * @param arr arr
     * @return arr
     */
    public static int[] selection(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int minIdx = i - 1;
            for (int j = i; j < arr.length; j++) {
                if (arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }
            swap(i - 1, minIdx, arr);
        }
        return arr;
    }


    /**
     * 归并排序
     * 请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
     * <p>
     * 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
     * <p>
     * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
     * <p>
     * 重复步骤 3 直到某一指针达到序列尾；
     * <p>
     * 将另一序列剩下的所有元素直接复制到合并序列尾。
     *
     * @param arr arr
     * @return arr
     */
    public static int[] merge(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int middle = arr.length >> 1;

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(merge(left), merge(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

    private static void swap(int i1, int i2, int[] arr) {
        int tmp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        insert(new int[]{
                                2, 0, 5, 4, -1, 6, 9, 1, 8
                        })
                )
        );
        System.out.println(
                Arrays.toString(
                        shell(new int[]{
                                2, 0, 5, 4, -1, 6, 9, 1, 8
                        })
                )
        );
        System.out.println(
                Arrays.toString(
                        bubble(new int[]{
                                2, 0, 5, 4, -1, 6, 9, 1, 8
                        })
                )
        );
        System.out.println(
                Arrays.toString(
                        selection(new int[]{
                                2, 0, 5, 4, -1, 6, 9, 1, 8
                        })
                )
        );
        System.out.println(
                Arrays.toString(
                        merge(new int[]{
                                2, 0, 5, 4, -1, 6, 9, 1, 8
                        })
                )
        );
    }
}
